package algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序:每次把数组分拆成两个子数组，分拆的依据是取一个中间数（一般取数组的第一个数字），
 * 一个子数组的所有元素都比中间数小，另一个子数组的所有元素都比中间数大，一直递归拆分，直到子数组只有一个元素为止
 * example: https://www.cnblogs.com/jilodream/p/5954916.html
 */
public class QuickSortTest {
    public static void main(String[] args) {
        int[] arr = { 1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19 };
        sort(arr);
        System.out.println("result arr = " + Arrays.toString(arr));
    }

    public static void sort(int[] arr){
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int begin, int end){
        if(begin >= end) return;

        int mid = partition(arr, begin, end);
        // 注意不要把mid再重新计算了
        quickSort(arr, begin, mid - 1);
        quickSort(arr, mid + 1, end);
    }

    public static int partition(int[] arr, int begin, int end){
        // 与midVal 相等的数字如何处理？放前面？还是后面？
        int mid = begin;
        // index用于保证每一个前面的数字都是小于arr[mid]
        int index = mid + 1;
        // 找到小于arr[mid]的数字跟arr[index]交换
        for(int i = index; i <= end; i++){
            if(arr[i] < arr[mid]){
                // 不等于的时候才交换
                if(i != index){
                    swap(arr, i, index);
                }
                index++;
            }
        }
        swap(arr, index - 1, mid);
        return index - 1;
    }

    public static void swap(int[] arr, int i , int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
